<html>
<head><meta charset="utf-8"><title>an approximate solver for chalk? · wg-traits · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/index.html">wg-traits</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html">an approximate solver for chalk?</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="184952568"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184952568" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184952568">(Jan 06 2020 at 20:23)</a>:</h4>
<p>One of the things that <span class="user-mention" data-user-id="116083">@pnkfelix</span> and I were discussing -- basically, maybe it would make sense to build something more like rustc's engine, but operating on lowered chalk predicates? rustc's engine is quirky but of course it works "well enough" for rustc today, and it might make it easier to adopt chalk into rustc sooner rather than later.</p>
<p>Following up from that, I was pondering another possible design, one closer to the older 'recursive' solver that chalk used to have before the SLG solver. In short, it was always looking for a <em>unique</em> solution, unlike the existing chalk-engine solver that is based around finding exact solutions (and then having an outer layer that stops asking for more answers). I do remember we had some problems where the recursive solver wasn't strong enough to handle some cases, though I can't remember exactly what (<span class="user-mention" data-user-id="131694">@scalexm</span> maybe remembers). </p>
<p>Anyway, I think that one of these two things might make sense as a way to get chalk integrated "sooner rather than later". But I think this is something to consider more as a second step, once we've integrated the chalk-solve crate into rustc.</p>



<a name="184952815"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184952815" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184952815">(Jan 06 2020 at 20:26)</a>:</h4>
<blockquote>
<p>build something more like rustc's engine, but operating on lowered chalk predicates?</p>
</blockquote>
<p>Can we refactor existing solver from within such that it operates on the said input format?</p>



<a name="184952825"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184952825" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184952825">(Jan 06 2020 at 20:26)</a>:</h4>
<p>(existing rustc solver that is)</p>



<a name="184952871"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184952871" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184952871">(Jan 06 2020 at 20:26)</a>:</h4>
<p>This has a benefit of having only two parallel solvers, and not three, at any given point in time)</p>



<a name="184953375"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953375" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953375">(Jan 06 2020 at 20:33)</a>:</h4>
<p>I wondered about that path</p>



<a name="184953389"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953389" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953389">(Jan 06 2020 at 20:33)</a>:</h4>
<p>I think it's roughly equivalent</p>



<a name="184953412"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953412" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953412">(Jan 06 2020 at 20:33)</a>:</h4>
<p>That is, I think the goal would be to build up the solver in chalk and then asap remove the one from rustc</p>



<a name="184953432"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953432" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953432">(Jan 06 2020 at 20:33)</a>:</h4>
<p>Well I guess the question is can we do it <em>gradually</em> within rustc</p>



<a name="184953438"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953438" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953438">(Jan 06 2020 at 20:33)</a>:</h4>
<p>I don't see how, but maybe</p>



<a name="184953489"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953489" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953489">(Jan 06 2020 at 20:34)</a>:</h4>
<p>Really the most important thing here -- probably -- is to figure out the caching questions for 'lowering'</p>



<a name="184953505"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953505" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953505">(Jan 06 2020 at 20:34)</a>:</h4>
<p>Also, a related question:</p>



<a name="184953524"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953524" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953524">(Jan 06 2020 at 20:34)</a>:</h4>
<p>I've been describing a design that merges chalk types with rust types by having two parallel definitions that will eventually merge</p>



<a name="184953552"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953552" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953552">(Jan 06 2020 at 20:35)</a>:</h4>
<p>But this could be a performance hazard, and I guess the goal should probably be to merge the type definitions sooner rather than later</p>



<a name="184953566"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953566" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953566">(Jan 06 2020 at 20:35)</a>:</h4>
<p>Probably "just" rote work within rustc</p>



<a name="184953588"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953588" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953588">(Jan 06 2020 at 20:35)</a>:</h4>
<p>(<em>That</em> could be done gradually, though)</p>



<a name="184953608"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953608" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953608">(Jan 06 2020 at 20:35)</a>:</h4>
<p>i.e., we could gradually refactor rustc's enum until it basically matches the chalk enum</p>



<a name="184953688"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/an%20approximate%20solver%20for%20chalk%3F/near/184953688" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/an.20approximate.20solver.20for.20chalk.3F.html#184953688">(Jan 06 2020 at 20:36)</a>:</h4>
<p>which would probably be good, since it might inform whether chalk's enum has the right set of variants (in particular, I think we might want to extract the integral / floating point types out, because of the way that rustc's integer literals work)</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>